#
# Created by Administrator on 2021/7/29 AT 15:16.
#
# 和0-1背包、完全背包的区别：
# 物品数量有限
def package(m, n, volume, value, number):
    """
    滚动数组
    每一行只与上一行有关
    :param m:  物品个数
    :param n:  背包容量
    :param volume:  每个物品的体积
    :param value:   每个物品的价值
    :param number:  每种物品最多几件
    :return:
    """
    dp = [0] * (1 + n)  # dp矩阵 注意维数都+1
    # 遍历物品
    for i in range(m):
        # 遍历背包容量  从后往前
        for j in range(n, 0, -1):
            for k in range(number[i] + 1):
                if j < k * volume[i]:
                    break
                # 按照0-1的思路，第i个物品拿k个
                dp[j] = max(dp[j], dp[j - k * volume[i]] + k * value[i])

        print(dp)
    return dp[n]


if __name__ == '__main__':
    print(package(5, 1000, [80, 40, 30, 40, 20], [20, 50, 50, 30, 20], [4, 9, 7, 6, 1]))
